package com.hyb.algorithm.data.struct.dp;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: huyanbing
 * @Date: 2021/9/6 6:48 下午
 *
 * 78. 子集
 * https://leetcode-cn.com/problems/subsets/
 * https://leetcode.wang/leetCode-78-Subsets.html
 *
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 */
public class Subsets {

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> res=new ArrayList<>();
        List<Integer> tempList=new ArrayList<>();

        backtrack(res,0,tempList,nums);

        return res;

    }

    public void backtrack( List<List<Integer>> res,int start,List<Integer> tempList, int[] nums){

        //添加 包括 []
        res.add(new ArrayList(tempList));


        for(int i=start;i<nums.length;i++){
            tempList.add(nums[i]);
            backtrack(res,i+1,tempList,nums);
            tempList.remove(tempList.size()-1);
        }

    }
}
